W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Jaś zamierza wyruszyć na wycieczkę po Bajtocji. Między miastami Bajtocji istnieją dwukierunkowe połączenia autobusowe. Jaś zastanawia się, jaka trasa tam i z powrotem kosztowałaby najmniej, jeśli dane połączenie może być użyte tylko raz (czyli po przejechaniu autobusem z A do B nie możemy nim wrócić z B do A). Pomóż Jasiowi rozwiązać jego problem.
Napisz program, który:
W pierwszym wierszu wejścia podane są dwie liczby naturalne, (liczba miast) i (liczba dwukierunkowych połączeń), , . W każdym z następnych wierszy znajdują się trzy liczby , , (, ): początek, koniec i koszt -tego połączenia.
Między daną parą miast istnieje co najwyżej jedno połączenie.
W pierwszym wierszu wyjścia ma się znajdować liczba odwieczonych miast (początek i koniec liczymy osobno) na najtańszej zamkniętej niepustej trasie. W następnym wierszu ma się znajować liczb naturalnych: numery kolejno odwiedzanych miast.
W przypadku istnienia wielu rozwiązań można wypisać dowolne z nich, w przypadku braku rozwiązań w jedynym wierszu wyjścia należy wpisać BRAK.
Dla danych wejściowych:
5 6 1 4 1 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20
poprawną odpowiedzią jest:
5 1 2 5 3 1
Autor zadania: Krzysztof Dulęba.